/* vim: set sw=8 ts=8 sts=8 expandtab: */
#include "Cmaid.h"
#include "cmaid_private.h"

/* for debug only, remove after */
#include <stdio.h>

/**
 * @defgroup Cmaid_Hash The Hash Implementation
 * @ingroup Implementations
 * @brief The hash implementation
 *
 * The hash table implementation provides a growing hash table used for fast
 * insertions, removes and look-ups. All these operations are in mean constant
 * in time, i.e. @em O(1) for the best case. Depending on the hash value
 * function, this can become linear in time, i.e. @em O(N), in the worst case
 * scenario. Keep this in mind and adjust your hash function to the hashed
 * data if you find the basic operations, not constant in time. Unlike like
 * in the @ref Cmaid_Tree "tree", the values are not lexically ordered.
 *
 * The hash table is implement with a growing bucket size, that means, once the
 * hash table table is too full, the bucket array is reallocated with a larger
 * size, and the nodes are re-insert. This happens automatically and you have
 * not to care about it. But it is important to know when using iterators.
 *
 * As soon as an iterator is attached to the hash table, the hash bucket size
 * is frozen, so that the order of the nodes is not changed. So doing massive
 * adds with an attached iterator may reduce the performance of the hash
 * table.
 */

#define PRIME_TABLE_MAX 21
#define PRIME_MIN 17
#define PRIME_MAX 16777213

#define CMAID_HASH_CHAIN_MAX 3

#define CMAID_HASH_COMPUTE(hash, hashcode) hashcode % cmaid_prime_table[hash->size]

#define CMAID_HASH_INCREASE(hash) \
                ((hash && cmaid_prime_table[hash->size] < PRIME_MAX) ? \
                (CMAID_CONTAINER(hash)->count > (cmaid_prime_table[hash->size]  \
                * CMAID_HASH_CHAIN_MAX)) : FALSE)
#define CMAID_HASH_REDUCE(hash) \
                ((hash && cmaid_prime_table[hash->size] > PRIME_MIN) ? \
                 CMAID_CONTAINER(hash)->count * 3 \
                 < cmaid_prime_table[hash->size-1] * CMAID_HASH_CHAIN_MAX : FALSE)
#define CMAID_HASH_FROZEN(hash) ((hash)->iter_list)

/** Type definition for the hash */
typedef struct Cmaid_Hash Cmaid_Hash;
/** Type definition for the hash node */
typedef struct Cmaid_Hash_Node Cmaid_Hash_Node;
/** Type definition for the hash node of the cache*/
typedef struct Cmaid_Hash_Cache_Node Cmaid_Hash_Cache_Node;
/** Type definition for the hash map */
typedef struct Cmaid_Hash_Map Cmaid_Hash_Map;
/** Type definition for the hash node of the map */
typedef struct Cmaid_Hash_Node_Pair Cmaid_Hash_Node_Pair;

#define CMAID_HASH(h) ((Cmaid_Hash *)(h))
#define CMAID_HASH_NODE(n) ((Cmaid_Hash_Node *)(n))
#define CMAID_HASH_CACHE_NODE(n) ((Cmaid_Hash_Cache_Node *)(n))
#define CMAID_HASH_CACHE_NODE_COUNT(n) CMAID_HASH_CACHE_NODE(n)->count
#define CMAID_HASH_MAP_VALUE_INFO(h) ((Cmaid_Hash_Map *)(h))->value_info
#define CMAID_HASH_MAP_NODE_VALUE(n) ((Cmaid_Hash_Node_Pair *)(n))->value

/**
 * @internal
 * @struct The hash node for the set
 */
struct Cmaid_Hash_Node
{
        Cmaid_Hash_Node *next;  /**< Pointer to the next node in the bucket
                                 list */
        void *key;              /**< The key for the data node */
};

/**
 * @internal
 * @struct The hash node for the cache
 */
struct Cmaid_Hash_Cache_Node
{
        Cmaid_Hash_Node node;   /**< The cache node inherits from the node */
        unsigned int count;     /**< The count of references */
};

/**
 * @internal
 * The hash node for the map
 */
struct Cmaid_Hash_Node_Pair
{
        Cmaid_Hash_Node node;
        void *value;
};

/**
 * @internal
 * The base structure for the hash table
 */
struct Cmaid_Hash
{
        Cmaid_Container container;
        Cmaid_Hash_Node **buckets;
        Cmaid_Iter *iter_list;
        const Cmaid_Value *key_info;
        int size;                /* An index into the table of primes to
                                   determine size */
};

/**
 * @internal
 * The extended structure for the map
 */
struct Cmaid_Hash_Map
{
        Cmaid_Hash hash;
        const Cmaid_Value *value_info;
};


static const int cmaid_prime_table[] =
{
        17, 31, 61, 127, 257, 509, 1021,
        2053, 4093, 8191, 16381, 32771, 65537, 131071, 262147, 524287, 1048573,
        2097143, 4194301, 8388617, 16777213
};


/* Private hash manipulation functions */
static void cmaid_hash_node_add(Cmaid_Hash *hash, unsigned int hash_code, 
                                        Cmaid_Hash_Node *node);
CMAID_INLINE int cmaid_hash_node_add_plain(Cmaid_Hash *hash,
                                        unsigned int hash_code, 
                                        Cmaid_Hash_Node *node);
static Cmaid_Hash_Node *cmaid_hash_node_get(Cmaid_Hash *hash,
                                        unsigned int hash_code,
                                        const void *key);
static Cmaid_Hash_Node *cmaid_hash_node_remove(Cmaid_Hash *hash,
                                        unsigned int hash_code,
                                        const void *key);
static int cmaid_hash_increase(Cmaid_Hash *hash);
static int cmaid_hash_decrease(Cmaid_Hash *hash);
CMAID_INLINE int cmaid_hash_rehash(Cmaid_Hash *hash, 
                                        Cmaid_Hash_Node **old_table,
                                        int old_size);
CMAID_INLINE Cmaid_Hash_Node *cmaid_hash_bucket_get(Cmaid_Hash *hash,
                                        Cmaid_Hash_Node *bucket, 
                                        const void *key,
                                        Cmaid_Hash_Node **prev);
static Cmaid_Hash_Node *cmaid_hash_bucket_remove(Cmaid_Hash *hash, int bucket,
                                        const void *key);
CMAID_INLINE void cmaid_hash_node_repair(Cmaid_Hash *hash, 
                                        unsigned int hash_code, 
                                        Cmaid_Hash_Node *node, 
                                        Cmaid_Hash_Node *new_node);
CMAID_INLINE void cmaid_hash_iter_update_remove(Cmaid_Hash *hash,
                                        int bucket, Cmaid_Hash_Node *node,
                                        Cmaid_Hash_Node *prev);

/* The common interface functions */
static void  cmaid_hash_iter_attach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_hash_iter_detach(Cmaid_Container *c, Cmaid_Iter *it);
static void  cmaid_hash_destroy(Cmaid_Container *c);
static int   cmaid_hash_dump(Cmaid_Container *c, FILE *file);
static void  cmaid_hash_clear(Cmaid_Container *c);
/* The set interface functions */
static void *cmaid_hash_set_add(Cmaid_Set *s, const void *data);
static void  cmaid_hash_set_remove(Cmaid_Set *s, const void *data);
static void *cmaid_hash_set_get(Cmaid_Set *s, const void *data);
CMAID_INLINE void cmaid_hash_single_node_free(Cmaid_Container *c, void *node);
/* The map interface functions */
static void *cmaid_hash_map_set(Cmaid_Map *m, const void *key, const void *data);
static void  cmaid_hash_map_remove(Cmaid_Map *m, const void *key);
static void *cmaid_hash_map_get(Cmaid_Map *m, const void *key);
static void  cmaid_hash_map_value_iter_attach(Cmaid_Map *m, Cmaid_Iter *it);
CMAID_INLINE void cmaid_hash_map_node_free(Cmaid_Container *c, void *n);
/* The cache interface functions */
static void *cmaid_hash_cache_instance(Cmaid_Cache *cache, const void *data);
static void  cmaid_hash_cache_release(Cmaid_Cache *cache, const void *data);
/* The common iterator interface functions */
static void  cmaid_hash_iter_start(Cmaid_Iter *it);
static void  cmaid_hash_iter_remove(Cmaid_Iter *it);
/* The key iter functions */
static void *cmaid_hash_key_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it);
static void *cmaid_hash_key_iter_index_goto(Cmaid_Iter *it, int index);
static void *cmaid_hash_key_iter_goto(Cmaid_Iter *it, const void *data);
static void *cmaid_hash_key_iter_current(Cmaid_Iter *it);
static void *cmaid_hash_key_iter_next(Cmaid_Iter *it);
static void *cmaid_hash_key_iter_previous(Cmaid_Iter *it);
/* The value iter functions */
static void *cmaid_hash_value_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it);
static void *cmaid_hash_value_iter_index_goto(Cmaid_Iter *it, int index);
static void *cmaid_hash_value_iter_goto(Cmaid_Iter *it, const void *data);
static void *cmaid_hash_value_iter_current(Cmaid_Iter *it);
static void *cmaid_hash_value_iter_next(Cmaid_Iter *it);
static void *cmaid_hash_value_iter_previous(Cmaid_Iter *it);
/* Iter helper */
static Cmaid_Hash_Node *cmaid_hash_iter_next(Cmaid_Iter *it);
static Cmaid_Hash_Node *cmaid_hash_iter_previous(Cmaid_Iter *it);

/*
 * The Interfaces
 */
const Cmaid_Set_Interface cmaid_hash_set_if =
{
        {
                CMAID_MAGIC_SET,
                cmaid_hash_clear,
                cmaid_hash_iter_attach,
                cmaid_hash_iter_detach,
                cmaid_hash_destroy,
                cmaid_hash_dump,
                cmaid_hash_single_node_free
        },
        cmaid_hash_set_add,
        cmaid_hash_set_remove,
        cmaid_hash_set_get
};

const Cmaid_Map_Interface cmaid_hash_map_if =
{
        {
                CMAID_MAGIC_MAP,
                cmaid_hash_clear,
                cmaid_hash_iter_attach,
                cmaid_hash_iter_detach,
                cmaid_hash_destroy,
                cmaid_hash_dump,
                cmaid_hash_map_node_free
        },
        cmaid_hash_map_set,
        cmaid_hash_map_remove,
        cmaid_hash_map_get,
        cmaid_hash_map_value_iter_attach
};

const Cmaid_Cache_Interface cmaid_hash_cache_if =
{
        {
                CMAID_MAGIC_CACHE,
                cmaid_hash_clear,
                cmaid_hash_iter_attach,
                cmaid_hash_iter_detach,
                cmaid_hash_destroy,
                cmaid_hash_dump,
                cmaid_hash_single_node_free
        },
        cmaid_hash_cache_instance,
        cmaid_hash_cache_release
};

const Cmaid_Iter_Interface cmaid_hash_key_iter_if =
{
        cmaid_hash_iter_start,
        cmaid_hash_key_iter_iter_goto,
        cmaid_hash_key_iter_index_goto,
        cmaid_hash_key_iter_goto,
        cmaid_hash_key_iter_current,
        cmaid_hash_key_iter_next,
        cmaid_hash_key_iter_previous,
        cmaid_hash_iter_remove
};

const Cmaid_Iter_Interface cmaid_hash_value_iter_if =
{
        cmaid_hash_iter_start,
        cmaid_hash_value_iter_iter_goto,
        cmaid_hash_value_iter_index_goto,
        cmaid_hash_value_iter_goto,
        cmaid_hash_value_iter_current,
        cmaid_hash_value_iter_next,
        cmaid_hash_value_iter_previous,
        cmaid_hash_iter_remove
};

/*
 * Utility functions
 */
CMAID_INLINE unsigned int
cmaid_hash_hashcode_get(Cmaid_Hash *hash, const void *key, unsigned int *size)
{
        if (!hash->key_info->hash)
                return cmaid_value_pointer_hash(key, size);

        return hash->key_info->hash(key, size);
}

CMAID_INLINE void
cmaid_hash_buckets_setup(Cmaid_Hash *hash)
{
        if (!hash->buckets)
        {
                hash->buckets = CALLOC(cmaid_prime_table[0],
                        sizeof(Cmaid_Hash_Node *));
                hash->size = 0;
        }
}
/*
 * Node Functions
 */
CMAID_INLINE void
cmaid_hash_single_node_free(Cmaid_Container *c, void *n)
{
        Cmaid_Hash *hash = CMAID_HASH(c);
        Cmaid_Hash_Node *node = n;
        cmaid_single_node_free(node, hash->key_info, node->key);
}

CMAID_INLINE void
cmaid_hash_map_node_free(Cmaid_Container *c, void *n)
{
        Cmaid_Hash *hash = CMAID_HASH(c);
        Cmaid_Hash_Node *node = n;
        cmaid_pair_node_free(node, hash->key_info, node->key,
                                CMAID_HASH_MAP_VALUE_INFO(hash),
                                CMAID_HASH_MAP_NODE_VALUE(node));
}

/*
 * Common Interface Functions
 */
static void
cmaid_hash_iter_attach(Cmaid_Container *c, Cmaid_Iter *it)
{
        it->interface = &cmaid_hash_key_iter_if;
        it->container = c;
        cmaid_hash_iter_start(it);

        /* insert into the iter list */
        it->next = CMAID_HASH(c)->iter_list;
        CMAID_HASH(c)->iter_list = it;        
}

static void
cmaid_hash_iter_detach(Cmaid_Container *c, Cmaid_Iter *it)
{
        Cmaid_Hash *hash = CMAID_HASH(c);
        cmaid_iterlist_remove(&hash->iter_list, it);
}

static void 
cmaid_hash_clear(Cmaid_Container *c)
{
        Cmaid_Hash *hash = CMAID_HASH(c);
        Cmaid_Container_Node_Free_Cb node_free;
        int i;

        if (!hash->buckets)
                return;

        node_free = CMAID_CONTAINER_FUNC(c)->node_free;

        for (i = 0; i < cmaid_prime_table[hash->size]; i++)
        {
                Cmaid_Hash_Node *list;
                Cmaid_Hash_Node *node;

                if (!hash->buckets[i])
                        continue;
                /*
                 * Remove the bucket list to avoid possible recursion
                 * on the free callbacks.
                 */
                list = hash->buckets[i];
                hash->buckets[i] = NULL;
                for (node = list; node; node = list)
                {
                        list = list->next;
                        node_free(c, node);
                }
        }
        FREE(hash->buckets);
        hash->buckets = NULL;
        CMAID_CONTAINER(hash)->count = 0;
}

static int 
cmaid_hash_dump(Cmaid_Container *c, FILE *file)
{
        Cmaid_Hash *hash = CMAID_HASH(c);
        Cmaid_Value_Stringify_Cb cb;
        char buffer[1024];
        unsigned int i;

        cb = hash->key_info->stringify ? hash->key_info->stringify :
                cmaid_value_pointer_stringify;

        fprintf(file, "digraph hash%p {\n", c);
        fprintf(file, "\tgraph [rankdir = \"LR\"];\n");

        /* first print the buckets */
        fprintf(file, "\tbuckets [\n\t\tlabel=\"buckets ");
        for (i = 0; i < cmaid_prime_table[hash->size]; i++)
        {
                if (hash->buckets[i])
                        fprintf(file, "|<f%d> %d ", i, i);
                else
                        fprintf(file, "| %d ", i, i);
        }
        fprintf(file, "\"\n\t\tshape=\"record\"\n\t]\n");

        /* and now the nodes */
        for (i = 0; i < cmaid_prime_table[hash->size]; i++)
        {
                Cmaid_Hash_Node *prev, *node;

                prev = NULL;
                for (node = hash->buckets[i]; node; node = node->next)
                {
                        /* print the node */
                        cb(node->key, buffer, sizeof(buffer));
                        fprintf(file, "n%p [label=\"%s\"];\n", node, buffer);
                        if (prev)
                                fprintf(file, "n%p -> n%p;\n", prev, node);
                        else
                                fprintf(file, "buckets:f%d -> n%p;\n", i, node);
                        prev = node;
                }
        }
        fprintf(file, "}\n");

        return TRUE;
}

static void 
cmaid_hash_destroy(Cmaid_Container *c)
{
        cmaid_container_clear(c);
        FREE(c);
}

/*
 * The Set Interface Functions
 */
/**
 * @param v The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used in the set
 * @return Returns a newly allocated @ref Cmaid_Set "set", an allocation error
 *        occurs, @c NULL is returned
 * @brief Creates a new set using the hash implementation
 *
 * This functions is creating a @ref Cmaid_Set "set" with the hash table
 * as implementation.
 */
Cmaid_Set *
cmaid_hash_set_new(const Cmaid_Value *v)
{
        Cmaid_Hash *new_hash = CALLOC(1, sizeof(Cmaid_Hash));
        if (!new_hash)
                return NULL;

        CMAID_CONTAINER_INTERFACE_SET(new_hash, &cmaid_hash_set_if);
        if (v)
                new_hash->key_info = v;
        else
                new_hash->key_info = &cmaid_value_pointer;

        return (Cmaid_Set *)new_hash;
}

static void *
cmaid_hash_set_add(Cmaid_Set *set, const void *key)
{
        Cmaid_Hash *hash = CMAID_HASH(set);
        unsigned int hash_code;
        Cmaid_Hash_Node *node;
        unsigned int size = 0;

        cmaid_hash_buckets_setup(hash);
        hash_code = cmaid_hash_hashcode_get(hash, key, &size);
        node = cmaid_hash_node_get(hash, hash_code, key);
        
        if (node)
        {
                if (hash->key_info->pointer.free && !hash->key_info->pointer.dup) 
                        hash->key_info->pointer.free((void *)key);
        }
        else
        {
                void *val;
                node = cmaid_single_node_new(sizeof(Cmaid_Hash_Node),
                                hash->key_info, key, size, &val);
                if (!node)
                        return NULL;
                
                node->key = val;
                cmaid_hash_node_add(hash, hash_code, node);
                return node->key;
        }

        return node->key;
}

static void
cmaid_hash_set_remove(Cmaid_Set *set, const void *key)
{
        Cmaid_Hash_Node *node;
        unsigned int hash_code;
        unsigned int dummy;
        Cmaid_Hash *hash = CMAID_HASH(set);

        /* Compute the position in the table */
        hash_code = cmaid_hash_hashcode_get(hash, key, &dummy);
        node = cmaid_hash_node_remove(hash, hash_code, key);
        if (!node)
                return;

        cmaid_hash_single_node_free(set, node);
}

static void *
cmaid_hash_set_get(Cmaid_Set *set, const void *key)
{
        Cmaid_Hash_Node *node;
        unsigned int hash_code;
        unsigned int dummy;
        Cmaid_Hash *hash = CMAID_HASH(set);

        hash_code = cmaid_hash_hashcode_get(hash, key, &dummy);
        node = cmaid_hash_node_get(hash, hash_code, key);
        if (!node)
                return NULL;

        return node->key;
}

/*
 * Cache Interface Functions
 */
/**
 * @param v The @ref Cmaid_Value "value structure" defining the type of the
 *        objects that are cached.
 * @return Returns a newly allocated @ref Cmaid_Cache "cache", an allocation
 *        error  occurs, @c NULL is returned
 * @brief Creates a new cache using the hash implementation
 *
 * This functions is creating a @ref Cmaid_Cache "cache" with the hash table
 * as implementation.
 */
Cmaid_Cache *
cmaid_hash_cache_new(const Cmaid_Value *v)
{
        Cmaid_Hash *new_hash = (Cmaid_Hash *)CALLOC(1, sizeof(Cmaid_Hash));
        if (!new_hash)
                return NULL;

        CMAID_CONTAINER_INTERFACE_SET(new_hash, &cmaid_hash_cache_if);
        cmaid_hash_buckets_setup(new_hash);
        if (v)
                new_hash->key_info = v;
        else
                new_hash->key_info = &cmaid_value_pointer;

        return (Cmaid_Cache *)new_hash;
}

static void *
cmaid_hash_cache_instance(Cmaid_Cache *c, const void *key)
{
        Cmaid_Hash *hash = CMAID_HASH(c);
        unsigned int hash_code;
        Cmaid_Hash_Node *node;
        unsigned int size = 0;

        cmaid_hash_buckets_setup(hash);
        hash_code = cmaid_hash_hashcode_get(hash, key, &size);
        node = cmaid_hash_node_get(hash, hash_code, key);
        
        if (node)
        {
                if (hash->key_info->pointer.free 
                                && !hash->key_info->pointer.dup) 
                        hash->key_info->pointer.free((void *)key);
                CMAID_HASH_CACHE_NODE_COUNT(node)++;
        }
        else
        {
                void *val;
                node = cmaid_single_node_new(sizeof(Cmaid_Hash_Cache_Node),
                                hash->key_info, (void *)key, size, &val);
                if (!node)
                        return NULL;
                
                node->key = val;
                CMAID_HASH_CACHE_NODE_COUNT(node) = 1;
                cmaid_hash_node_add(hash, hash_code, node);
                return node->key;
        }

        return node->key;
}

static void
cmaid_hash_cache_release(Cmaid_Cache *c, const void *key)
{
        Cmaid_Hash *hash = CMAID_HASH(c);
        Cmaid_Hash_Node *node;
        Cmaid_Hash_Node *prev = NULL;
        unsigned int hash_code;
        unsigned int bucket;
        unsigned int dummy;

        if (!hash->buckets)
                return;

        /* Compute the position in the table */
        hash_code = cmaid_hash_hashcode_get(hash, key, &dummy);
        bucket = CMAID_HASH_COMPUTE(hash, hash_code);

        node = cmaid_hash_bucket_get(hash, hash->buckets[bucket], key, &prev);
        if (!node)
                return;

        if (--CMAID_HASH_CACHE_NODE_COUNT(node) == 0)
        {
                /* ok we have actually to remove the node */
                /* first update the iters */
                cmaid_hash_iter_update_remove(hash, bucket, node, prev);
                /*remove the node */
                if (!prev)
                        hash->buckets[bucket] = node->next;
                else
                        prev->next = node->next;
                /* and reduce the count */
                CMAID_CONTAINER(hash)->count--;

                cmaid_hash_single_node_free(c, node);
        }
}

/*
 * The Map Interface Functions
 */
static void
cmaid_hash_map_value_iter_attach(Cmaid_Container *c, Cmaid_Iter *it)
{
        it->interface = &cmaid_hash_value_iter_if;
        it->container = c;
        cmaid_hash_iter_start(it);

        /* insert into the iter list */
        it->next = CMAID_HASH(c)->iter_list;
        CMAID_HASH(c)->iter_list = it;        
}

/**
 * @param key The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used for the key object.
 * @param value The @ref Cmaid_Value "value structure" defining the type of the
 *        objects used for the value object.
 * @return Returns a newly allocated @ref Cmaid_Map "map", an allocation error
 *        occurs, @c NULL is returned.
 * @brief Creates a new map using the hash implementation
 *
 * This functions is creating a @ref Cmaid_Map "map" with the hash table as
 * implementation.
 */
Cmaid_Map *
cmaid_hash_map_new(const Cmaid_Value *key, const Cmaid_Value *value)
{
        Cmaid_Hash *new_hash = CALLOC(1, sizeof(Cmaid_Hash_Map));
        if (!new_hash)
                return NULL;

        CMAID_CONTAINER_INTERFACE_SET(new_hash, &cmaid_hash_map_if);
        if (key)
                new_hash->key_info = key;
        else
                new_hash->key_info = &cmaid_value_pointer;
        
        if (value)
                CMAID_HASH_MAP_VALUE_INFO(new_hash) = value;
        else
                CMAID_HASH_MAP_VALUE_INFO(new_hash) = &cmaid_value_pointer;

        return (Cmaid_Map *)new_hash;
}

static void *
cmaid_hash_map_set(Cmaid_Map *map, const void *key, const void *value)
{
        Cmaid_Hash *hash = CMAID_HASH(map);
        unsigned int hash_code;
        Cmaid_Hash_Node *node;
        unsigned int size = 0;

        if (value == NULL)
                cmaid_hash_map_remove(map, key);

        cmaid_hash_buckets_setup(hash);
        hash_code = cmaid_hash_hashcode_get(hash, key, &size);
        node = cmaid_hash_node_get(hash, hash_code, key);
        
        if (node)
        {
                Cmaid_Hash_Node *new_node;
                void *ptr_key;

                if (hash->key_info->pointer.free && !hash->key_info->pointer.dup) 
                        hash->key_info->pointer.free((void *)key);

                if (CMAID_HASH_MAP_VALUE_INFO(hash)->pointer.free)
                        CMAID_HASH_MAP_VALUE_INFO(hash)->pointer.free(CMAID_HASH_MAP_NODE_VALUE(node));

                new_node = cmaid_pair_node_renew(node, 
                                sizeof(Cmaid_Hash_Node_Pair),
                                size, CMAID_HASH_MAP_VALUE_INFO(hash),
                                value, &ptr_key);

                if (node != new_node)
                        cmaid_hash_node_repair(hash, hash_code, node, new_node);
                return CMAID_HASH_MAP_NODE_VALUE(new_node) = ptr_key;
        }
        else
        {
                void *vptr;
                void *kptr;
                node = cmaid_pair_node_new(sizeof(Cmaid_Hash_Node_Pair),
                                hash->key_info, key, size, &kptr,
                                CMAID_HASH_MAP_VALUE_INFO(hash), value, 0,
                                &vptr);
                if (!node)
                        return NULL;
                
                node->key = kptr;
                CMAID_HASH_MAP_NODE_VALUE(node) = vptr;
                cmaid_hash_node_add(hash, hash_code, node);
                return kptr;
        }

        return node->key;
}

static void
cmaid_hash_map_remove(Cmaid_Map *map, const void *key)
{
        Cmaid_Hash_Node *node;
        unsigned int hash_code;
        unsigned int dummy;
        Cmaid_Hash *hash = CMAID_HASH(map);

        /* Compute the position in the table */
        hash_code = cmaid_hash_hashcode_get(hash, key, &dummy);
        node = cmaid_hash_node_remove(hash, hash_code, key);
        if (!node)
                return;

        cmaid_hash_map_node_free(map, node);
}

static void *
cmaid_hash_map_get(Cmaid_Map *map, const void *key)
{
        Cmaid_Hash_Node *node;
        unsigned int hash_code;
        unsigned int dummy;
        Cmaid_Hash *hash = CMAID_HASH(map);

        hash_code = cmaid_hash_hashcode_get(hash, key, &dummy);
        node = cmaid_hash_node_get(hash, hash_code, key);
        if (!node)
                return NULL;

        return CMAID_HASH_MAP_NODE_VALUE(node);
}


/*
 * Helper functions
 */
static void
cmaid_hash_node_add(Cmaid_Hash *hash, unsigned int hash_code, Cmaid_Hash_Node *node)
{
        int bucket;
        Cmaid_Iter *iter;

        /* Check to see if the hash needs to be resized */
        if (!CMAID_HASH_FROZEN(hash) && CMAID_HASH_INCREASE(hash))
                cmaid_hash_increase(hash);

        bucket = cmaid_hash_node_add_plain(hash, hash_code, node);

        /* update indices of the iterators */
        for (iter = hash->iter_list; iter; iter = iter->next)
        {
                if (iter->bucket >= bucket)
                        iter->index++;
        }

        CMAID_CONTAINER(hash)->count++;
}

CMAID_INLINE int
cmaid_hash_node_add_plain(Cmaid_Hash *hash, unsigned int hash_code,
                        Cmaid_Hash_Node *node)
{
        unsigned int hash_val;

        hash_val = CMAID_HASH_COMPUTE(hash, hash_code);

        /* Prepend the node to the list at the index position */
        node->next = hash->buckets[hash_val];
        hash->buckets[hash_val] = node;

        return hash_val;
}

static Cmaid_Hash_Node *
cmaid_hash_node_get(Cmaid_Hash *hash, unsigned int hash_code, const void *key)
{
        Cmaid_Hash_Node *node = NULL;
        unsigned int hash_val;
        Cmaid_Hash_Node *prev = NULL;

        if (!hash->buckets)
                return NULL;

        /* Compute the position in the table */
        hash_val = CMAID_HASH_COMPUTE(hash, hash_code);

        /* Grab the bucket at the specified position */
        if (!hash->buckets[hash_val])
                return NULL;

        node = cmaid_hash_bucket_get(hash, hash->buckets[hash_val], key, &prev);
        /*
         * Move matched node to the front of the list as it's likely
         * to be searched for again soon. Don't do that if the hash
         * is frozen!
         */
        if (node && prev && !CMAID_HASH_FROZEN(hash))
        {
                prev->next = node->next;
                node->next = hash->buckets[hash_val];
                hash->buckets[hash_val] = node;
        }

        return node;
}

static Cmaid_Hash_Node *
cmaid_hash_node_remove(Cmaid_Hash *hash, unsigned int hash_code, const void *key)
{
        Cmaid_Hash_Node *node;
        unsigned int hash_val;

        /* Compute the position in the table */
        hash_val = CMAID_HASH_COMPUTE(hash, hash_code);

        node = cmaid_hash_bucket_remove(hash, hash_val, key);

        if (!CMAID_HASH_FROZEN(hash) && CMAID_HASH_REDUCE(hash))
                cmaid_hash_decrease(hash);

        return node;
}


/*
 * @brief Search the hash bucket for a specified key
 * @param hash the hash table to retrieve the comparison function
 * @param bucket the list to search for the key
 * @param key the key to search for in the list
 * @return Returns NULL on error or not found, the found node on success
 */
CMAID_INLINE Cmaid_Hash_Node *
cmaid_hash_bucket_get(Cmaid_Hash *hash, Cmaid_Hash_Node *bucket,
                        const void *key, Cmaid_Hash_Node **prev)
{
        Cmaid_Hash_Node *node = NULL;

        /*
         * Traverse the list to find the desired node, if the node is in the
         * list, then return the node.
         */
        if (hash->key_info->cmp)
        {
                for (node = bucket; node; node = node->next)
                {
                        if (hash->key_info->cmp(node->key, key) == 0)
                                break;
                        *prev = node;
                }
        }
        else
        {
                for (node = bucket; node; node = node->next)
                {
                        if (node->key == key)
                                break;
                        *prev = node;
                }
        }

        return node;
}

static Cmaid_Hash_Node *
cmaid_hash_bucket_remove(Cmaid_Hash *hash, int bucket, const void *key)
{
        Cmaid_Hash_Node *node;
        Cmaid_Hash_Node *prev = NULL;

        /*
         * If their is a list that could possibly hold the key/value pair
         * traverse it and remove the hash node.
         */
        if (!hash->buckets[bucket])
                return NULL;

        node = cmaid_hash_bucket_get(hash, hash->buckets[bucket], key, &prev);

        /* if we haven't found the node we are done */
        if (!node)
                return NULL;
        
        /* update the indices of the iterators, we are doing that before
         * we actually removed the node, so we can use 
         * cmaid_hash_iter_previous */
        cmaid_hash_iter_update_remove(hash, bucket, node, prev);

        /* and finally remove the node */
        if (!prev)
                hash->buckets[bucket] = node->next;
        else
                prev->next = node->next;
        /* and reduce the count */
        CMAID_CONTAINER(hash)->count--;

        return node;
}

/*
 * @brief Increase the size of the hash table by approx.  2 * current size
 * @param hash the hash table to increase the size of
 * @return Returns TRUE on success, FALSE on error
 */
static int
cmaid_hash_increase(Cmaid_Hash *hash)
{
        void *old;

        /* Max size reached so return FALSE */
        if ((cmaid_prime_table[hash->size] == PRIME_MAX) 
                        || (hash->size == PRIME_TABLE_MAX))
                return FALSE;

        /*
         * Increase the size of the hash and save a pointer to the old data
         */
        hash->size++;
        old = hash->buckets;

        /*
         * Allocate a new bucket area, of the new larger size
         */
        hash->buckets = CALLOC(cmaid_prime_table[hash->size], sizeof(Cmaid_Hash_Node *));

        /*
         * Make sure the allocation succeeded, if not replace the old data and
         * return a failure.
         */
        if (!hash->buckets)
        {
                hash->buckets = old;
                hash->size--;
                return FALSE;
        }

        /*
         * Now move all of the old data into the new bucket area
         */
        if (cmaid_hash_rehash(hash, old, hash->size - 1))
        {
                FREE(old);
                return TRUE;
        }

        /*
         * Free the old buckets regardless of success.
         */
        FREE(old);

        return FALSE;
}

/*
 * @brief Decrease the size of the hash table by < 1/2 * current size
 * @param hash the hash table to decrease the size of
 * @return Returns TRUE on success, FALSE on error
 */
static int
cmaid_hash_decrease(Cmaid_Hash *hash)
{
        Cmaid_Hash_Node **old;

        if (cmaid_prime_table[hash->size] == PRIME_MIN)
                return FALSE;

        /*
         * Decrease the hash size and store a pointer to the old data
         */
        hash->size--;
        old = hash->buckets;

        /*
         * Allocate a new area to store the data
         */
        hash->buckets = CALLOC(cmaid_prime_table[hash->size],
                                        sizeof(Cmaid_Hash_Node *));

        /*
         * Make sure allocation succeeded otherwise return to the previous
         * state
         */
        if (!hash->buckets)
        {
                hash->buckets = old;
                hash->size++;
                return FALSE;
        }

        if (cmaid_hash_rehash(hash, old, hash->size + 1))
        {
                FREE(old);
                return TRUE;
        }

        FREE(old);
        return FALSE;
}

/*
 * @brief Rehash the nodes of a table into the hash table
 * @param hash the hash to place the nodes of the table
 * @param table the table to remove the nodes from and place in hash
 * @return Returns TRUE on success, FALSE on error
 */
CMAID_INLINE int
cmaid_hash_rehash(Cmaid_Hash *hash, Cmaid_Hash_Node **old_table, int old_size)
{
        int i;
        Cmaid_Hash_Node *old;
        Cmaid_Value_Hash_Cb hashcode_get;

        /* find the right hash function */
        hashcode_get = (!hash->key_info->hash) 
                ? cmaid_value_pointer_hash : hash->key_info->hash;

        for (i = 0; i < cmaid_prime_table[old_size]; i++)
        {
                /* Hash into a new list to avoid loops of rehashing the same
                 * nodes */
                while ((old = old_table[i]))
                {
                        unsigned int hash_code;
                        unsigned int dummy;

                        old_table[i] = old->next;
                        hash_code = hashcode_get(old->key, &dummy);
                        cmaid_hash_node_add_plain(hash, hash_code, old);
                }
        }

        return TRUE;
}

CMAID_INLINE void
cmaid_hash_node_repair(Cmaid_Hash *hash, unsigned int hash_code, 
                        Cmaid_Hash_Node *node, Cmaid_Hash_Node *new_node)
{
        Cmaid_Hash_Node *list;
        int bucket = CMAID_HASH_COMPUTE(hash, hash_code);

        list = hash->buckets[bucket];
        if (list == node)
                hash->buckets[bucket] = new_node;
        else
        {
                for (; list->next; list = list->next)
                {
                        if (list->next == node)
                        {
                                list->next = new_node;
                                return;
                        }
                }
                fprintf(stderr, "haven't found a node!\n");
        }
        cmaid_iterlist_repair(hash->iter_list, node, new_node);
}

CMAID_INLINE void
cmaid_hash_iter_update_remove(Cmaid_Hash *hash, int bucket,
                                Cmaid_Hash_Node *node, Cmaid_Hash_Node *prev)
{
        Cmaid_Iter *iter;

        for (iter = hash->iter_list; iter; iter = iter->next)
        {
                if (iter->bucket == bucket)
                {
                        Cmaid_Hash_Node *find = node;

                        if (iter->current == find)
                        {
                                if (!prev)
                                        cmaid_hash_iter_previous(iter);
                                else
                                {
                                        iter->index--;
                                        iter->current = prev;
                                }
                        }
                        else
                        {
                                while (find && find != iter->current)
                                        find = find->next;
                                if (find)
                                        iter->index--;
                        }
                }
                else if (iter->bucket > bucket)
                        iter->index--;
        }
}

/*
 * The Iterator functions
 */
/* The common iterator interface functions */
static void
cmaid_hash_iter_start(Cmaid_Iter *it)
{
        it->current = NULL;
        it->index = -1;
        it->bucket = -1;
}

static void
cmaid_hash_iter_remove(Cmaid_Iter *it)
{
        Cmaid_Hash *hash = CMAID_HASH(it->container);
        Cmaid_Container *c = CMAID_CONTAINER(hash);
        
        if (it->current)
        {
                void * node = cmaid_hash_bucket_remove(hash, it->bucket, 
                                        CMAID_HASH_NODE(it->current)->key);
                CMAID_CONTAINER_FUNC(c)->node_free(c, node);
        }
}

/* helper functions */
static Cmaid_Hash_Node *
cmaid_hash_iter_next(Cmaid_Iter *it)
{
        const Cmaid_Hash *hash = CMAID_HASH(it->container);
        const int size = cmaid_prime_table[hash->size];

        if (!hash->buckets)
                return NULL;
        /* if we at the start the index is -1 so ++ is here correct, too.
         * if we at the last node, we will correct the index at the end */
        it->index++;
        if (it->current && CMAID_HASH_NODE(it->current)->next)
                return it->current = CMAID_HASH_NODE(it->current)->next;
        
        /* here it is the same if we are at the start, bucket is -1 */
        it->bucket++;
        while (it->bucket < size)
        {
                if (hash->buckets[it->bucket])
                        return it->current = hash->buckets[it->bucket];
                it->bucket++;
        }

        /* we are at the end */
        cmaid_hash_iter_start(it);
        return NULL;
}

static Cmaid_Hash_Node *
cmaid_hash_iter_previous(Cmaid_Iter *it)
{
        const Cmaid_Hash *hash = CMAID_HASH(it->container);
        const int size = cmaid_prime_table[hash->size];
        
        if (!hash->buckets)
                return NULL;

        if (it->current)
        {
                Cmaid_Hash_Node *find = hash->buckets[it->bucket];

                it->index--;
                /* if we are not on the first node we need to find the node
                 * before */
                if (!find)
                        printf("what happened here?\nWe are in a non-existing"
                                        " list\n");
                if (find != it->current)
                {
                        while (find->next != it->current)
                                find = find->next;
                        
                        return it->current = find;
                }
                it->bucket--;
        }
        else
        {
                it->index = CMAID_CONTAINER(it->container)->count - 1;
                it->bucket = size - 1;
        }
        
        while (it->bucket >= 0)
        {
                if (hash->buckets[it->bucket])
                {
                        Cmaid_Hash_Node *last = hash->buckets[it->bucket];
                        /* find the last node in the chain */
                        while (last->next)
                                last = last->next;

                        return it->current = last;
                }
                it->bucket--;
        }

        /* we are at the beginning */
        cmaid_hash_iter_start(it);
        return NULL;
}

static Cmaid_Hash_Node *
cmaid_hash_iter_index_goto(Cmaid_Iter *it, int index)
{
        const int count = CMAID_CONTAINER(it->container)->count;
        int i;

        if (count == 0 || index >= count || index < 0)
        {
                cmaid_hash_iter_start(it);
                return NULL;
        }

        if (index < it->index)
                cmaid_hash_iter_start(it);

        for (i = it->index; i != index; i++)
                cmaid_hash_iter_next(it);

        return it->current;
}

/* The key iter functions */
static void *
cmaid_hash_key_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it)
{
        if (!to_it || it->container != to_it->container)
                return NULL;

        it->index = to_it->index;
        it->current = to_it->current;
        it->bucket = to_it->bucket;
        return (it->current) ? CMAID_HASH_NODE(it->current)->key : NULL;
}

static void *
cmaid_hash_key_iter_index_goto(Cmaid_Iter *it, int index)
{
        Cmaid_Hash_Node *node = cmaid_hash_iter_index_goto(it, index);
        return (node) ? node->key : NULL;
}

static void *
cmaid_hash_key_iter_goto(Cmaid_Iter *it, const void *data)
{
        void * found;

        cmaid_hash_iter_start(it);
        while ((found = cmaid_hash_key_iter_next(it)) && found != data)
                ;

        return found;
}

static void *
cmaid_hash_key_iter_current(Cmaid_Iter *it)
{
        return (it->current) ? CMAID_HASH_NODE(it->current)->key : NULL;
}

static void *
cmaid_hash_key_iter_next(Cmaid_Iter *it)
{
        Cmaid_Hash_Node *node = cmaid_hash_iter_next(it);
        return (node) ? node->key : NULL;
}

static void *
cmaid_hash_key_iter_previous(Cmaid_Iter *it)
{
        Cmaid_Hash_Node *node = cmaid_hash_iter_previous(it);
        return (node) ? node->key : NULL;
}

/* The value iter functions */
static void *
cmaid_hash_value_iter_iter_goto(Cmaid_Iter *it, const Cmaid_Iter *to_it)
{
        if (!to_it || it->container != to_it->container)
                return NULL;

        it->index = to_it->index;
        it->current = to_it->current;
        it->bucket = to_it->bucket;
        return (it->current) ? CMAID_HASH_MAP_NODE_VALUE(it->current) : NULL;
}
static void *
cmaid_hash_value_iter_index_goto(Cmaid_Iter *it, int index)
{
        Cmaid_Hash_Node *node = cmaid_hash_iter_index_goto(it, index);
        return (node) ? CMAID_HASH_MAP_NODE_VALUE(node) : NULL;
}

static void *
cmaid_hash_value_iter_goto(Cmaid_Iter *it, const void *data)
{
        void * found;

        cmaid_hash_iter_start(it);
        while ((found = cmaid_hash_value_iter_next(it)) && found != data)
                ;

        return found;
}

static void *
cmaid_hash_value_iter_current(Cmaid_Iter *it)
{
        return (it->current) ? CMAID_HASH_MAP_NODE_VALUE(it->current) : NULL;
}

static void *
cmaid_hash_value_iter_next(Cmaid_Iter *it)
{
        Cmaid_Hash_Node *node = cmaid_hash_iter_next(it);
        return (node) ? CMAID_HASH_MAP_NODE_VALUE(node) : NULL;
}

static void *
cmaid_hash_value_iter_previous(Cmaid_Iter *it)
{
        Cmaid_Hash_Node *node = cmaid_hash_iter_previous(it);
        return (node) ? CMAID_HASH_MAP_NODE_VALUE(node) : NULL;
}

